package practice.hot100;

import java.util.*;

public class Solution491 {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return res;
    }

    LinkedList<Integer> tmp = new LinkedList<>();

    public void backtracking(int[] nums, int index) {
        if (index >= nums.length) return;

        Set<Integer> set = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (!tmp.isEmpty() && tmp.getLast() > nums[i]) continue;
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
                tmp.add(nums[i]);
                if (tmp.size() > 1) res.add(new ArrayList<>(tmp));
                backtracking(nums, i + 1);
                tmp.removeLast();
            }
        }
    }
}
